package com.dy.数组.高级.最小窗口子字符串;
/*
给定一个字符串 S 和一个字符串 T，请在 S 中找出包含 T 所有字母的最小子串。

示例：

输入: S = "ADOBECODEBANC", T = "ABC"
输出: "BANC"
说明：

如果 S 中不存这样的子串，则返回空字符串 ""。
如果 S 中存在这样的子串，我们保证它是唯一的答案。
 */

import java.util.HashMap;

/**
 * S = "ADBANC"，T = "ABC"，那么我们肉眼遍历一遍S呗，首先第一个是A，嗯很好，T中有，第二个是D，T中没有，不理它，第三个是B，
 * 嗯很好，T中有，第四个又是A，多了一个，礼多人不怪嘛，收下啦，第五个是N，一边凉快去，第六个终于是C了，那么貌似好像需要整个S串，
 * 其实不然，我们注意之前有多一个A，但么我们就算去掉第一个A，也没事，因为第四个A可以代替之，第二个D也可以去掉，因为不在T串中，
 * 第三个B就不能再去掉了，不然就没有B了。所以最终的答案就"BANC"了。通过上面的描述，你有没有发现一个有趣的现象，我们是先扩展，
 * 再收缩，就好像一个窗口一样，先扩大右边界，然后再收缩左边界，上面的例子中我们是右边界无法扩大了后才开始收缩左边界，实际上对于复杂的例子，
 * 有可能是扩大右边界，然后缩小一下左边界，然后再扩大右边界等等。这就很像一个不停滑动的窗口了，这就是大名鼎鼎的滑动窗口Sliding Window了，
 * 简直是神器啊，能解很多子串，子数组，子序列等等的问题，是必须要熟练掌握的啊！
 * <p>
 * 下面我们来考虑用代码来实现，先来回答一下前面埋下的伏笔，为啥要用HashMap，而不是HashSet，现在应该很显而易见了吧，
 * 因为要统计T串中字母的个数，而不是仅仅看某个字母是否在T串中出现。统计好T串中字母的个数了之后，我们开始遍历S串，
 * 对于S中的每个遍历到的字母，都在HashMap中的映射值减1，如果减1后的映射值仍大于等于0，说明当前遍历到的字母是T串中的字母，
 * 我们使用一个计数器cnt，使其自增1。当cnt和T串字母个数相等时，说明此时的窗口已经包含了T串中的所有字母，此时更新一个minLen和结果res，
 * 这里的minLen是我们维护的一个全局变量，用来记录出现过的包含T串所有字母的最短的子串的长度，结果res就是这个最短的子串。
 * 然后我们要开始收缩左边界，由于我们遍历的时候，对映射值减了1，所以此时去除字母的时候，就要把减去的1加回来，此时如果加1后的值大于0了，
 * 说明此时我们少了一个T中的字母，那么cnt值就要减1了，然后移动左边界left。那么你可能会疑问，对于不在T串中的字母的映射值也这么加呀减呀的，
 * 真的大丈夫（带胶布）吗？其实没啥事，因为对于不在T串中的字母，我们减1后，变-1，cnt不会增加，之后收缩左边界的时候，映射值加1后为0，
 * <p>
 * cnt也不会减少，所以并没有什么影响啦，下面是具体的步骤啦：
 * <p>
 * - 我们最开始先扫描一遍T，把对应的字符及其出现的次数存到HashMap中。
 * <p>
 * - 然后开始遍历S，就把遍历到的字母对应的HashMap中的value减一，如果减1后仍大于等于0，cnt自增1。
 * <p>
 * - 如果cnt等于T串长度时，开始循环，纪录一个字串并更新最小字串值。然后将子窗口的左边界向右移，
 * 如果某个移除掉的字母是T串中不可缺少的字母，那么cnt自减1，表示此时T串并没有完全匹配。
 */
public class Solution {
    //map里存放的是还需要匹配字母的次数
    public String minWindow2(String s, String t) {
        if(s.length()<t.length())return "";
        HashMap<Character, Integer> map = new HashMap<>();

        for (char c : t.toCharArray()) {
            Integer count = map.get(c);
            if (count == null) {
                map.put(c, 1);

            } else {
                map.put(c, count+1);
            }
        }

        int slow = 0, minLen = Integer.MAX_VALUE, matchCount = 0,index =0;

        for (int fast = 0; fast < s.length(); fast++) {
            char c = s.charAt(fast);
            Integer count = map.get(c);
            if (count == null) {
                continue;
            }
            //如果count是1，则说明找到匹配
            if (count == 1) {
                matchCount++;
            }
            map.put(c, count - 1);

            while(matchCount ==map.size()){
                //找到一个合理的字符串
                if(fast-slow+1<minLen){
                    minLen = fast-slow+1;
                    index = slow;
                }
                char leftCharacter = s.charAt(slow++);
                Integer leftCount = map.get(leftCharacter);
                if(leftCount==null){
                    continue;
                }
                map.put(leftCharacter,leftCount+1);
                if(leftCount==0){
                    matchCount--;
                }
            }

        }
        return minLen ==Integer.MAX_VALUE?"":s.substring(index,index+minLen);
    }


    public String minWindow(String s, String t) {
//        HashMap<Character,Integer> map = new HashMap<>();
//        int cnt=0;
//        for(char c:t.toCharArray()) map.put(c,map.getOrDefault(c,0)+1);
//        for(int i=0;i<s.length();i++){
//            if(map.getOrDefault(s.charAt(i),0)>0){
//                cnt++;
//                map.put(s.charAt(i),map.get(s.charAt(i))-1);
//            }
//        }
        if (s.length() < t.length() || s.length() == 0 || s == null || t == null || t.length() == 0)
            return "";
        int[] map = new int[255];
        for (int i = 0; i < t.length(); i++) {
            map[t.charAt(i)]++;
        }
        //双指针遍历源字符串s
        int begin = 0, end = 0;
        //最小字符串的起点
        int minBegin = 0;
        //最小字符串的长度
        int res = Integer.MAX_VALUE;
        //用来记录匹配到字符的个数，如果count == t.length()意味着找到一个匹配的字串
        int count = 0;

        while (end < s.length()) {
            //这里可理解为缺失字符的个数，==0时则表示 这个字符匹配够了，==1则表示仍需要再匹配一个该字符
            if (map[s.charAt(end)] > 0) count++;
            //不需要匹配的字符，其值此时小于0
            map[s.charAt(end)]--;

            end++;

            //匹配到一个字串
            while (count == t.length()) {
                //比较字串长度，更新字串信息
                if (end - begin < res) {
                    res = end - begin;
                    minBegin = begin;
                }
                //如果首指针对应字符是目标字符之一，则跳出循环
                if (map[s.charAt(begin)] == 0)
                    count--;
                //首指针对应字符的哈希值还原
                map[s.charAt(begin)]++;
                //首指针右移
                begin++;
            }
        }
        return res == Integer.MAX_VALUE ? "" : s.substring(minBegin, minBegin + res);
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        solution.minWindow2("aa", "aa");
    }
}
